package 剑指Offer专项突破;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

/**
 * @Author zhang lei
 * @Date 2022-05-03 15:51
 */
public class Algo057 {

    /**
     * 057 值和下标之差都在给定的范围之内
     * @param nums
     * @param k
     * @param t
     * @return
     */
    public static boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        //感觉是用滑动窗口做，先满足下标之差<= k, 值相同挑近的
        if(nums.length == 0 || nums.length == 1) {
            return false;
        }

        //先按o(n^2)计算
        for (int i = 0; i < nums.length; i++) {
            for (int length = 1; length <= k && (i+length) < nums.length; length++) {
                long a = nums[i];
                long b = nums[i+length];
                long sum = Math.abs( a - b);

                if( sum <= t) {
                    return true;
                }
            }
        }

        return false;

    }

    /**
     * 057的 TreeSet解法
     * @param nums
     * @param k
     * @param t
     * @return
     */
    public static boolean containsNearbyAlmostDuplicate2(int[] nums, int k, int t) {
        TreeSet<Long> treeSet = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            Long lower = treeSet.floor((long) nums[i]);
            if(lower != null && nums[i]- lower<=t) {
                return true;
            }

            Long upper = treeSet.ceiling((long) nums[i]);
            if(upper != null && upper - nums[i] <= t) {
                return true;
            }

            treeSet.add((long) nums[i]);
            if(i>=k) {
                treeSet.remove((long)nums[i-k]);
            }
        }

        return false;

    }

    public static void main(String[] args) {
        System.out.println(containsNearbyAlmostDuplicate2(new int[]{1,5,9,13,1,9}, 2, 3));
    }
}
